// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

/**
 * A linked-list node which holds data for cache entry such as key, value, size.
 * @param {string} key
 * @param {T} value
 * @param {number} size
 * @constructor
 * @template T
 */
function LRUCacheNode(key, value, size) {
  /** @type {string} */
  this.key = key;

  /** @type {T} */
  this.value = value;

  /** @type {number} */
  this.size = size;

  /** @type {LRUCacheNode} */
  this.next = null;

  /** @type {LRUCacheNode} */
  this.prev = null;
}

/**
 * Container of the list of cache nodes.
 * @constructor
 */
function LRUCacheList() {
  /** @private {!LRUCacheNode} */
  this.sentinelTail_ = new LRUCacheNode('sentinel', null, 0);

  /** @private {LRUCacheNode} */
  this.head_ = this.sentinelTail_;
}

/**
 * Removes a node from this list.
 * @param {!LRUCacheNode} node
 */
LRUCacheList.prototype.remove = function(node) {
  if (node.prev)
    node.prev.next = node.next;
  if (node.next)
    node.next.prev = node.prev;
  if (node === this.head_)
    this.head_ = node.next;
  node.prev = null;
  node.next = null;
};

/**
 * Adds a node at the head of this list.
 * @param {!LRUCacheNode} node
 */
LRUCacheList.prototype.prepend = function(node) {
  node.prev = null;
  node.next = this.head_;
  node.next.prev = node;
  this.head_ = node;
};

/**
 * Returns the last node of the list, or null if the list has no nodes.
 * @return {LRUCacheNode}
 */
LRUCacheList.prototype.lastNode = function() {
  return this.sentinelTail_.prev;
};

/**
 * Cache management class implementing LRU algorithm.
 * @param {number} maxSize Maximum total size of items this cache can hold. When
 *     items are put without specifying their sizes, their sizes are treated as
 *     1 and the |maxSize| can be interpreted as the maximum number of items.
 *     If items are put with specifying their sizes in bytes, the |maxSize| can
 *     be interpreted as the maximum number of bytes.
 * @constructor
 * @template T
 */
function LRUCache(maxSize) {
  /** @private {number} */
  this.totalSize_ = 0;

  /** @private {number} */
  this.maxSize_ = maxSize;

  /** @private {!LRUCacheList} */
  this.list_ = new LRUCacheList();

  /** @private {!Object<!LRUCacheNode>} */
  this.nodes_ = {};
}

/**
 * Returns a cached item corresponding to the given key. The referenced item
 * will be the most recently used item and won't be evicted soon.
 * @param {string} key
 * @return {T}
 */
LRUCache.prototype.get = function(key) {
  var node = this.nodes_[key];
  if (!node)
    return null;

  this.moveNodeToHead_(node);
  return node.value;
};

/**
 * Returns a cached item corresponding to the given key without making the
 * referenced item the most recently used item.
 * @param {string} key
 * @return {T}
 */
LRUCache.prototype.peek = function(key) {
  var node = this.nodes_[key];
  if (!node)
    return null;

  return node.value;
};

/**
 * Returns true if the cache contains the key.
 * @param {string} key
 * @return {boolean}
 */
LRUCache.prototype.hasKey = function(key) {
  return key in this.nodes_;
};

/**
 * Saves an item in this cache. The saved item will be the most recently used
 * item and won't be evicted soon. If an item with the same key already exists
 * in the cache, the existing item's value and size will be updated and the item
 * will become the most recently used item.
 * @param {string} key Key to find the cached item later.
 * @param {T} value Value of the item to be cached.
 * @param {number=} opt_size Size of the put item. If not specified, the size is
 *     regarded as 1. If the size is larger than the |maxSize_|, put operation
 *     will be ignored keeping cache state unchanged.
 */
LRUCache.prototype.put = function(key, value, opt_size) {
  var size = opt_size ? opt_size : 1;
  if (size > this.maxSize_)
    return;

  var node = this.nodes_[key];

  while (this.totalSize_ + size - (node ? node.size : 0) > this.maxSize_) {
    this.evictLastNode_();
    // The referenced node may be evicted, so it needs to be updated.
    node = this.nodes_[key];
  }

  if (node) {
    this.updateNode_(node, value, size);
    this.moveNodeToHead_(node);
  } else {
    node = new LRUCacheNode(key, value, size);
    this.prependNode_(node);
  }
};

/**
 * Removes an item from the cache.
 * @param {string} key
 */
LRUCache.prototype.remove = function(key) {
  var node = this.nodes_[key];
  if (node)
    this.removeNode_(node);
};

/**
 * Returns the cache size.
 * @return {number}
 */
LRUCache.prototype.size = function() {
  return this.totalSize_;
};

/**
 * Updates max size of the cache.
 * @param {number} value New max size.
 */
LRUCache.prototype.setMaxSize = function(value) {
  this.maxSize_ = value;
  while (this.totalSize_ > this.maxSize_) {
    this.evictLastNode_();
  }
};

/**
 * Returns the max size of the cache.
 * @return {number}
 */
LRUCache.prototype.getMaxSize = function() {
  return this.maxSize_;
};

/**
 * Evicts the oldest cache node.
 * @private
 */
LRUCache.prototype.evictLastNode_ = function() {
  var lastNode = this.list_.lastNode();
  if (!lastNode)
    throw new Error('No more nodes to evict.');

  this.removeNode_(lastNode);
};

/**
 * Removes given node from this cache store completely.
 * @param {!LRUCacheNode} node
 * @private
 */
LRUCache.prototype.removeNode_ = function(node) {
  this.list_.remove(node);
  this.totalSize_ -= node.size;
  console.assert(this.totalSize_ >= 0);
  console.assert(!!this.nodes_[node.key]);
  delete this.nodes_[node.key];
};

/**
 * Prepends given node to the head of list.
 * @param {!LRUCacheNode} node
 * @private
 */
LRUCache.prototype.prependNode_ = function(node) {
  this.list_.prepend(node);
  this.totalSize_ += node.size;
  console.assert(this.totalSize_ <= this.maxSize_);
  console.assert(!this.nodes_[node.key]);
  this.nodes_[node.key] = node;
};

/**
 * Updates the given nodes size and value.
 * @param {!LRUCacheNode} node
 * @param {T} value
 * @param {number} size
 * @private
 */
LRUCache.prototype.updateNode_ = function(node, value, size) {
  this.totalSize_ += size - node.size;
  console.assert(this.totalSize_ >= 0 && this.totalSize_ <= this.maxSize_);
  node.value = value;
  node.size = size;
};

/**
 * Moves the given node to the head of the linked list.
 * @param {!LRUCacheNode} node
 * @private
 */
LRUCache.prototype.moveNodeToHead_ = function(node) {
  this.list_.remove(node);
  this.list_.prepend(node);
};
